// 力扣918. 环形子数组的最大和
import java.util.*;
class Solution {
    // 最小子数组和 (minSum) 代表数组中连续元素的最小和。
    // 如果从总和中减去这个最小和，剩下的部分就是不包含这个最小子数组的连续元素的和。
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0;
        int maxSum = Integer.MIN_VALUE;
        int currentMax = 0;
        int minSum = Integer.MAX_VALUE;
        int currentMin = 0;

        for (int num : nums) {
            total += num;

            // 计算最大子数组和（标准Kadane算法）
            currentMax = Math.max(num, currentMax + num);
            maxSum = Math.max(maxSum, currentMax);

            // 计算最小子数组和
            currentMin = Math.min(num, currentMin + num);
            minSum = Math.min(minSum, currentMin);
        }

        // 特殊情况：所有数都是负数
        if (maxSum < 0) {
            return maxSum;
        }

        // 比较两种情况：不跨越边界和跨越边界
        return Math.max(maxSum, total - minSum);
    }
}


// 力扣162. 寻找峰值
class Solution1 {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}



// 力扣502. IPO
class Solution2 {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        // 创建项目列表并按资本要求排序
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        Arrays.sort(projects, (a, b) -> a[0] - b[0]);

        // 最大堆存储可承担项目的利润
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        int i = 0;
        while (k > 0) {
            // 将所有当前可承担的项目加入堆
            while (i < n && projects[i][0] <= w) {
                maxHeap.offer(projects[i][1]);
                i++;
            }

            // 如果没有可承担的项目，跳出循环
            if (maxHeap.isEmpty()) {
                break;
            }

            // 选择利润最大的项目
            w += maxHeap.poll();
            k--;
        }

        return w;
    }
}